package com.smh;


import org.junit.jupiter.api.Test;

import java.util.Iterator;

/**
 * @author shiminghui
 * @date 2025/2/17 16:55
 * @description: TODO
 */
public class _021_双端队列_链表 {


    @Test
    public void test1() {

        MyDeque<Integer> integers = new MyDeque<>();
        integers.offerFirst(1);
        integers.offerLast(2);

        for (Integer integer : integers) {
            System.out.println(integer);
        }

    }


    private class MyDeque<T> implements Iterable<T> {

        private final Node<T> sentinelNode = new Node<>();
        private int size;
        private int capacity;

        {
            sentinelNode.next = sentinelNode;
            sentinelNode.prev = sentinelNode;
        }

        public MyDeque(int capacity) {
            this.capacity = capacity;
        }

        public MyDeque() {
            this(10);
        }

        public boolean offerFirst(T data) {
            if (isFull()) {
                return false;
            }

            Node<T> a = sentinelNode;
            Node<T> b = sentinelNode.next;
            Node<T> newNode = new Node<>(data, a, b);
            a.next = newNode;
            b.prev = newNode;
            size++;
            return true;
        }

        public boolean offerLast(T data) {
            if (isFull()) {
                return false;
            }

            Node<T> a = sentinelNode.prev;
            Node<T> b = sentinelNode;
            Node<T> newNode = new Node<>(data, a, b);
            a.next = newNode;
            b.prev = newNode;
            size++;
            return true;
        }

        public T pollFirst() {
            if (isEmpty()) {
                return null;
            }
            Node<T> a = sentinelNode;
            Node<T> b = sentinelNode.next;
            Node<T> c = b.next;
            a.next = c;
            c.prev = a;
            size--;
            return b.data;
        }

        public T pollLast() {
            if (isEmpty()) {
                return null;
            }
            Node<T> b = sentinelNode.prev;
            Node<T> c = sentinelNode;
            Node<T> a = b.prev;
            a.next = c;
            c.prev = a;
            size--;
            return b.data;
        }

        public T peekFirst() {
            if (isEmpty()) {
                return null;
            }
            return sentinelNode.next.data;
        }

        public T peekLast() {
            if (isEmpty()) {
                return null;
            }
            return sentinelNode.prev.data;
        }

        public boolean isEmpty() {
            if (size == 0) {
                return true;
            }
            return false;
        }

        public boolean isFull() {
            if (size == capacity) {
                return true;
            }
            return false;
        }


        @Override
        public Iterator<T> iterator() {
            return new Iterator<T>() {
                private Node<T> s = sentinelNode.next;

                @Override
                public boolean hasNext() {
                    return s != sentinelNode;
                }

                @Override
                public T next() {
                    T data = s.data;
                    s = s.next;
                    return data;
                }
            };
        }


        private static class Node<T> {

            private T data;
            private Node<T> next;
            private Node<T> prev;

            public Node(T data, Node<T> prev, Node<T> next) {
                this.data = data;
                this.next = next;
                this.prev = prev;
            }

            public Node(T data) {
                this.data = data;
            }

            public Node() {
            }

        }

    }

}
